package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;

/**
 * <p> description: 桶排序</p>
 *
 * @author tanzc
 * @date 2022/1/27
 **/
public class BucketSort {

    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort();
        int num = 10, max = num * 5;
        int[] arr = ArrayUtils.randomoffset(num, max, 100);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
        ArrayUtils.printArray(arr1);

        System.out.print("桶排序-----time: ");
        Date start = new Date();
        int[] arr2 = bucketSort.bucket(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
        ArrayUtils.printArray(arr2);
    }

    /**
     * 桶排序，是普通计数排序的进阶版，通过将原数组序列元素分到不同的几个桶，先对桶内元素排序，然后再将所有桶元素合到一起
     * 普通计数排序可以认为是将所有相同元素放到一个桶里，而桶排序是将具有相同映射函数结果的元素放到一个桶里
     * 这里其实要注意，我个人觉得计数排序和桶排序只是在这一点上有一点相似之处，在后续操作上他们存在很大差别，所以我并不认为->
     * ->这两个排序很类似
     *
     * 所谓的映射函数，大多为一些普通的大小分段函数从，比如12个数分3个桶，那么三个桶内元素的原数组索引分别为1、2、3、4，5、6、7、8，9、10、11、12
     * 由于桶排序的效率如何，主要取决于每个桶内采用的排序方法，所以对于桶排序这里不做过多解释，直接复制的博客代码
     * 一般来说，在将元素放入桶中的时候，就可以进行插入排序的操作了，所以不用在元素全入桶后再分别做排序操作
     *
     * 由于桶排序按照某种映射函数关系来对数组元素分桶，因此，并不能保证在创建桶时确切知道每个桶的大小（可能是我还没理解透，->
     * ->但目前我认为在创建桶是是无法确定桶容量的），所以采用原始固定大小数组的方法来分配桶不合适，容易造成空间浪费在，
     * 这里建议使用bucket2
     *
     *
     * @param arr
     * @return
     */
    public int[] bucket(int[] arr) {
        int max = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 计算桶数量
        int bucketNum = (max - min) / arr.length + 1;
        // 计算每个桶的元素数量，目前我没想到能确定桶容量的方法
        // 因为桶数量是根据数组元素最大值与最小值与数组大小算出的，那么桶容量应该也可以大致确定
        // 懒得想了
        // 看了下博客，算桶容量的时候(max -min) / bucketNum + 1这样，应该是可以大概确定桶容量的
        // 不过还得考虑不是每个桶都能装满，后续排序与组合的时候还麻烦，还是懒得用原始的数组搞了
        int bucketSize = (max -min) / bucketNum - 1;
        int[][] bucketArr = new int[bucketNum][bucketSize];
        // 将数组元素装入桶
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / arr.length;
            bucketArr[num][(arr[i] - min) % bucketSize] = arr[i];
        }
        // 对每个桶排序
        InsertionSort insertionSort = new InsertionSort();
        for (int i = 0; i < bucketNum; i++) {
            insertionSort.insertion(bucketArr[i]);
        }
        int[] result = new int[arr.length];
        for (int i = 0; i < bucketNum; i++) {
            for (int j = 0; j < bucketSize; j++) {
                result[i * j + j] = bucketArr[i][j];
            }
        }

        return result;
    }

    public int[] bucket2(int[] arr) {
        int max = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        int[] result = new int[arr.length];
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                result[index++] = bucketArr.get(i).get(j);
            }
        }

//        版权声明：本文为CSDN博主「str_818」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
//        原文链接：https://blog.csdn.net/qq_27124771/article/details/87651495

        return result;
    }
}
